// 二叉链表法存储

#include "stdio.h"
#include "string.h"
#include "malloc.h"

#define OK 1
#define ERROR 0

typedef int Status;
typedef char TElemType;

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

int GetHeight(BiTree T);//返回二叉树T的高度

Status InitBiTree(BiTree &T) {
    T = NULL;
    return OK;
}//初始化为空树

Status CreateBiTree(BiTree &T) {
    TElemType c;
    scanf("%c", &c);
    if (c == '#')
        T = NULL;
    else {
        T = (BiTree) malloc(sizeof(BiTNode));
        T->data = c;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}//按先序遍历序列输入二叉树中结点的值（一个字符），#号表示空树

void PreOrderTraverse(BiTree T) {
    if (T) {
        printf("%c", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);

    }
}//输出根结点T的二叉树先序遍历序列

void InOrderTraverse(BiTree T) {
    if (T) {
        InOrderTraverse(T->lchild);
        printf("%c", T->data);
        InOrderTraverse(T->rchild);

    }
}//输出根结点T的二叉树中序遍历序列

void PostOrderTraverse(BiTree T) {
    if (T) {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c", T->data);

    }
}//输出根结点T的二叉树后序遍历序列

int GetHeight(BiTree T) {
    if (T) {
        int h1 = GetHeight(T->lchild);
        int h2 = GetHeight(T->rchild);
        return h1 > h2 ? h1 + 1 : h2 + 1;
    } else
        return 0;
} //返回二叉树T的高度